home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume14 / splay-tree < prev    next >
Encoding:
Internet Message Format  |  1988-05-08  |  41.9 KB

  1. Subject:  v14i087:  Splay tree library
  2. Newsgroups: comp.sources.unix
  3. Sender: sources
  4. Approved: rsalz@uunet.UU.NET
  5.  
  6. Submitted-by: Dave Brower <rtech!llama!daveb>
  7. Posting-number: Volume 14, Issue 87
  8. Archive-name: splay-tree
  9.  
  10. [  Kinda like AVL or balanced tree stuff, but not really.  --r$ ]
  11.  
  12. Here is a library for working with the splay trees Tarjan talked about
  13. in his ACM Turing Lecture.  I use it for symbol tables and the like.
  14. Others might want to change the key type and the use of strcmp as the
  15. ordering function.
  16.  
  17. It is a transliteration from Pascal code given me by Doug Jones at the U
  18. of Iowa.  Send thank you notes to him as jones@cs.uiowa.edu.
  19.  
  20. There is a man page and a Makefile for "libsptree.a."  I would be
  21. shocked, shocked indeed to find any critical system dependencies.  
  22. (Some of the statistics might want to be longs on 16 bit machines to
  23. avoid overflow).
  24.  
  25. Users must supply their own emalloc() function.  The cavalier might
  26. do "-Demalloc=malloc" during the compilation.
  27.  
  28. -dB
  29.  
  30. #!/bin/sh
  31. # This is a shell archive, meaning:
  32. # 1. Remove everything above the #!/bin/sh line.
  33. # 2. Save the resulting text in a file.
  34. # 3. Execute the file with /bin/sh (not csh) to create the files:
  35. #    Makefile
  36. #    spaux.c
  37. #    spdaveb.c
  38. #    sptree.3
  39. #    sptree.c
  40. #    sptree.h
  41. # This archive created: Wed Feb 10 19:41:38 1988
  42. export PATH; PATH=/bin:$PATH
  43. if test -f 'Makefile'
  44. then
  45.     echo shar: over-writing existing file "'Makefile'"
  46. fi
  47. sed 's/^X//' << \SHAR_EOF > 'Makefile'
  48. X#
  49. X# makefile for splay tree library
  50. X
  51. Xall:    libsptree.a
  52. X
  53. Xlibsptree.a:    sptree.o spaux.o spdaveb.o
  54. X    ar rvu libsptree.a sptree.o spaux.o spdaveb.o
  55. X
  56. SHAR_EOF
  57. if test -f 'spaux.c'
  58. then
  59.     echo shar: over-writing existing file "'spaux.c'"
  60. fi
  61. sed 's/^X//' << \SHAR_EOF > 'spaux.c'
  62. X/*
  63. X  spaux.c:  This code implements the following operations on an event-set
  64. X  or priority-queue implemented using splay trees:
  65. X  
  66. X  n = sphead( q )        n is the head item in q (not removed).
  67. X  spdelete( n, q )        n is removed from q.
  68. X  n = spnext( np, q )        n is the successor of np in q.
  69. X  n = spprev( np, q )        n is the predecessor of np in q.
  70. X  spenqbefore( n, np, q )    n becomes the predecessor of np in q.
  71. X  spenqafter( n, np, q )    n becomes the successor of np in q.
  72. X  
  73. X  In the above, n and np are pointers to single items (type
  74. X  SPBLK *); q is an event-set (type SPTREE *),
  75. X  The type definitions for these are taken
  76. X  from file sptree.h.  All of these operations rest on basic
  77. X  splay tree operations from file sptree.c.
  78. X  
  79. X  The basic splay tree algorithms were originally presented in:
  80. X  
  81. X  Self Adjusting Binary Trees,
  82. X  by D. D. Sleator and R. E. Tarjan,
  83. X  Proc. ACM SIGACT Symposium on Theory
  84. X  of Computing (Boston, Apr 1983) 235-245.
  85. X  
  86. X  The operations in this package supplement the operations from
  87. X  file splay.h to provide support for operations typically needed
  88. X  on the pending event set in discrete event simulation.  See, for
  89. X  example,
  90. X  
  91. X  Introduction to Simula 67,
  92. X  by Gunther Lamprecht, Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
  93. X  (Chapter 14 contains the relevant discussion.)
  94. X  
  95. X  Simula Begin,
  96. X  by Graham M. Birtwistle, et al, Studentlitteratur, Lund, 1979.
  97. X  (Chapter 9 contains the relevant discussion.)
  98. X  
  99. X  Many of the routines in this package use the splay procedure,
  100. X  for bottom-up splaying of the queue.  Consequently, item n in
  101. X  delete and item np in all operations listed above must be in the
  102. X  event-set prior to the call or the results will be
  103. X  unpredictable (eg:  chaos will ensue).
  104. X  
  105. X  Note that, in all cases, these operations can be replaced with
  106. X  the corresponding operations formulated for a conventional
  107. X  lexicographically ordered tree.  The versions here all use the
  108. X  splay operation to ensure the amortized bounds; this usually
  109. X  leads to a very compact formulation of the operations
  110. X  themselves, but it may slow the average performance.
  111. X  
  112. X  Alternative versions based on simple binary tree operations are
  113. X  provided (commented out) for head, next, and prev, since these
  114. X  are frequently used to traverse the entire data structure, and
  115. X  the cost of traversal is independent of the shape of the
  116. X  structure, so the extra time taken by splay in this context is
  117. X  wasted.
  118. X  
  119. X  This code was written by:
  120. X  Douglas W. Jones with assistance from Srinivas R. Sataluri
  121. X  
  122. X  Translated to C by David Brower, daveb@rtech.uucp
  123. X  
  124. X */
  125. X
  126. X# include    "sptree.h"
  127. X
  128. X
  129. X/*----------------
  130. X *
  131. X * sphead() --    return the "lowest" element in the tree.
  132. X *
  133. X *    returns a reference to the head event in the event-set q,
  134. X *    represented as a splay tree; q->root ends up pointing to the head
  135. X *    event, and the old left branch of q is shortened, as if q had
  136. X *    been splayed about the head element; this is done by dequeueing
  137. X *    the head and then making the resulting queue the right son of
  138. X *    the head returned by spdeq; an alternative is provided which
  139. X *    avoids splaying but just searches for and returns a pointer to
  140. X *    the bottom of the left branch
  141. X */
  142. XSPBLK *
  143. Xsphead( q )
  144. X
  145. Xregister SPTREE * q;
  146. X
  147. X{
  148. X    register SPBLK * x;
  149. X    
  150. X    /* splay version, good amortized bound */
  151. X    x = spdeq( q->root );
  152. X    if( x != NULL )
  153. X    {
  154. X        x->rightlink = q->root;
  155. X        x->leftlink = NULL;
  156. X        x->uplink = NULL;
  157. X        if( q->root != NULL )
  158. X        q->root->uplink = x;
  159. X    }
  160. X    q->root = x;
  161. X    
  162. X    /* alternative version, bad amortized bound,
  163. X       but faster on the average */
  164. X    
  165. X# if 0
  166. X    x = q->root;
  167. X    while( x->leftlink != NULL )
  168. X    x = x->leftlink;
  169. X# endif
  170. X    
  171. X    return( x );
  172. X    
  173. X} /* sphead */
  174. X
  175. X
  176. X
  177. X/*----------------
  178. X *
  179. X * spdelete() -- Delete node from a tree.
  180. X *
  181. X *    n is deleted from q; the resulting splay tree has been splayed
  182. X *    around its new root, which is the successor of n
  183. X *
  184. X */
  185. Xvoid
  186. Xspdelete( n, q )
  187. X
  188. Xregister SPBLK * n;
  189. Xregister SPTREE * q;
  190. X
  191. X{
  192. X    register SPBLK * x;
  193. X    
  194. X    splay( n, q );
  195. X    x = spdeq( q->root->rightlink );
  196. X    if( x == NULL )        /* empty right subtree */
  197. X    {
  198. X        q->root = q->root->leftlink;
  199. X        q->root->uplink = NULL;
  200. X    }
  201. X    else            /* non-empty right subtree */
  202. X    {
  203. X        x->uplink = NULL;
  204. X        x->leftlink = q->root->leftlink;
  205. X        x->rightlink = q->root->rightlink;
  206. X        if( x->leftlink != NULL )
  207. X        x->leftlink->uplink = x;
  208. X        if( x->rightlink != NULL )
  209. X        x->rightlink->uplink = x;
  210. X        q->root = x;
  211. X    }
  212. X    
  213. X} /* spdelete */
  214. X
  215. X
  216. X
  217. X/*----------------
  218. X *
  219. X * spnext() -- return next higer item in the tree, or NULL.
  220. X *
  221. X *    return the successor of n in q, represented as a splay tree; the
  222. X *    successor becomes the root; two alternate versions are provided,
  223. X *    one which is shorter, but slower, and one which is faster on the
  224. X *    average because it does not do any splaying
  225. X *
  226. X */
  227. XSPBLK *
  228. Xspnext( n, q )
  229. X
  230. Xregister SPBLK * n;
  231. Xregister SPTREE * q;
  232. X
  233. X{
  234. X    register SPBLK * next;
  235. X    register SPBLK * x;
  236. X    
  237. X    /* splay version */
  238. X    splay( n, q );
  239. X    x = spdeq( n->rightlink );
  240. X    if( x != NULL )
  241. X    {
  242. X        x->leftlink = n;
  243. X        n->uplink = x;
  244. X        x->rightlink = n->rightlink;
  245. X        n->rightlink = NULL;
  246. X        if( x->rightlink != NULL )
  247. X        x->rightlink->uplink = x;
  248. X        q->root = x;
  249. X        x->uplink = NULL;
  250. X    }
  251. X    next = x;
  252. X    
  253. X    /* shorter slower version;
  254. X       deleting last "if" undoes the amortized bound */
  255. X    
  256. X# if 0
  257. X    splay( n, q );
  258. X    x = n->rightlink;
  259. X    if( x != NULL )
  260. X    while( x->leftlink != NULL )
  261. X        x = x->leftlink;
  262. X    next = x;
  263. X    if( x != NULL )
  264. X    splay( x, q );
  265. X# endif
  266. X    
  267. X    return( next );
  268. X    
  269. X} /* spnext */
  270. X
  271. X
  272. X
  273. X/*----------------
  274. X *
  275. X * spprev() -- return previous node in a tree, or NULL.
  276. X *
  277. X *    return the predecessor of n in q, represented as a splay tree;
  278. X *    the predecessor becomes the root; an alternate version is
  279. X *    provided which is faster on the average because it does not do
  280. X *    any splaying
  281. X *
  282. X */
  283. XSPBLK *
  284. Xspprev( n, q )
  285. X
  286. Xregister SPBLK * n;
  287. Xregister SPTREE * q;
  288. X
  289. X{
  290. X    register SPBLK * prev;
  291. X    register SPBLK * x;
  292. X    
  293. X    /* splay version;
  294. X       note: deleting the last "if" undoes the amortized bound */
  295. X    
  296. X    splay( n, q );
  297. X    x = n->leftlink;
  298. X    if( x != NULL )
  299. X    while( x->rightlink != NULL )
  300. X        x = x->rightlink;
  301. X    prev = x;
  302. X    if( x != NULL )
  303. X    splay( x, q );
  304. X    
  305. X    return( prev );
  306. X    
  307. X} /* spprev */
  308. X
  309. X
  310. X
  311. X/*----------------
  312. X *
  313. X * spenqbefore() -- insert node before another in a tree.
  314. X *
  315. X *    returns pointer to n.
  316. X *
  317. X *    event n is entered in the splay tree q as the immediate
  318. X *    predecessor of n1; in doing so, n1 becomes the root of the tree
  319. X *    with n as its left son
  320. X *
  321. X */
  322. XSPBLK *
  323. Xspenqbefore( n, n1, q )
  324. X
  325. Xregister SPBLK * n;
  326. Xregister SPBLK * n1;
  327. Xregister SPTREE * q;
  328. X
  329. X{
  330. X    splay( n1, q );
  331. X    n->key = n1->key;
  332. X    n->leftlink = n1->leftlink;
  333. X    if( n->leftlink != NULL )
  334. X    n->leftlink->uplink = n;
  335. X    n->rightlink = NULL;
  336. X    n->uplink = n1;
  337. X    n1->leftlink = n;
  338. X    
  339. X    return( n );
  340. X    
  341. X} /* spenqbefore */
  342. X
  343. X
  344. X
  345. X/*----------------
  346. X *
  347. X * spenqafter() -- enter n after n1 in tree q.
  348. X *
  349. X *    returns a pointer to n.
  350. X *
  351. X *    event n is entered in the splay tree q as the immediate
  352. X *    successor of n1; in doing so, n1 becomes the root of the tree
  353. X *    with n as its right son
  354. X */
  355. XSPBLK *
  356. Xspenqafter( n, n1, q )
  357. X
  358. Xregister SPBLK * n;
  359. Xregister SPBLK * n1;
  360. Xregister SPTREE * q;
  361. X
  362. X{
  363. X    splay( n1, q );
  364. X    n->key = n1->key;
  365. X    n->rightlink = n1->rightlink;
  366. X    if( n->rightlink != NULL )
  367. X    n->rightlink->uplink = n;
  368. X    n->leftlink = NULL;
  369. X    n->uplink = n1;
  370. X    n1->rightlink = n;
  371. X    
  372. X    return( n );
  373. X    
  374. X} /* spenqafter */
  375. X
  376. X
  377. SHAR_EOF
  378. if test -f 'spdaveb.c'
  379. then
  380.     echo shar: over-writing existing file "'spdaveb.c'"
  381. fi
  382. sed 's/^X//' << \SHAR_EOF > 'spdaveb.c'
  383. X/*
  384. X * spdaveb.c -- daveb's new splay tree functions.
  385. X *
  386. X * The functions in this file provide an interface that is nearly
  387. X * the same as the hash library I swiped from mkmf, allowing
  388. X * replacement of one by the other.  Hey, it worked for me!
  389. X *
  390. X * splookup() -- given a key, find a node in a tree.
  391. X * spinstall() -- install an item in the tree, overwriting existing value.
  392. X * spfhead() -- fast (non-splay) find the first node in a tree.
  393. X * spftail() -- fast (non-splay) find the last node in a tree.
  394. X * spscan() -- forward scan tree from the head.
  395. X * sprscan() -- reverse scan tree from the tail.
  396. X * spfnext() -- non-splaying next.
  397. X * spfprev() -- non-splaying prev.
  398. X * spstats() -- make char string of stats for a tree.
  399. X *
  400. X * Written by David Brower, daveb@rtech.uucp 1/88.
  401. X */
  402. X
  403. X
  404. X# include "sptree.h"
  405. X
  406. X/* USER SUPPLIED! */
  407. X
  408. Xextern char *emalloc();
  409. X
  410. X
  411. X/*----------------
  412. X *
  413. X * splookup() -- given key, find a node in a tree.
  414. X *
  415. X *    Splays the found node to the root.
  416. X */
  417. XSPBLK *
  418. Xsplookup( key, q )
  419. X
  420. Xregister char * key;
  421. Xregister SPTREE * q;
  422. X
  423. X{
  424. X    register SPBLK * n;
  425. X    register int Sct;
  426. X    register int c;
  427. X
  428. X    /* find node in the tree */
  429. X    n = q->root;
  430. X    c = ++(q->lkpcmps);
  431. X    q->lookups++;
  432. X    while( n && (Sct = STRCMP( key, n->key ) ) )
  433. X    {
  434. X    c++;
  435. X    n = ( Sct < 0 ) ? n->leftlink : n->rightlink;
  436. X    }
  437. X    q->lkpcmps = c;
  438. X
  439. X    /* reorganize tree around this node */
  440. X    if( n != NULL )
  441. X    splay( n, q );
  442. X
  443. X    return( n );
  444. X}
  445. X
  446. X
  447. X
  448. X/*----------------
  449. X *
  450. X * spinstall() -- install an entry in a tree, overwriting any existing node.
  451. X *
  452. X *    If the node already exists, replace its contents.
  453. X *    If it does not exist, then allocate a new node and fill it in.
  454. X */
  455. X
  456. XSPBLK *
  457. Xspinstall( key, data, datb, q )
  458. X
  459. Xregister char * key;
  460. Xregister char * data;
  461. Xregister char * datb;
  462. Xregister SPTREE *q;
  463. X
  464. X{
  465. X    register SPBLK *n;
  466. X
  467. X    if( NULL == ( n = splookup( key, q ) ) )
  468. X    {
  469. X    n = (SPBLK *) emalloc( sizeof( *n ) );
  470. X    n->key = key;
  471. X    n->leftlink = NULL;
  472. X    n->rightlink = NULL;
  473. X    n->uplink = NULL;
  474. X    spenq( n, q );
  475. X    }
  476. X
  477. X    n->data = data;
  478. X    n->datb = datb;
  479. X
  480. X    return( n );
  481. X}
  482. X
  483. X
  484. X
  485. X
  486. X/*----------------
  487. X *
  488. X * spfhead() --    return the "lowest" element in the tree.
  489. X *
  490. X *    returns a reference to the head event in the event-set q.
  491. X *    avoids splaying but just searches for and returns a pointer to
  492. X *    the bottom of the left branch.
  493. X */
  494. XSPBLK *
  495. Xspfhead( q )
  496. X
  497. Xregister SPTREE * q;
  498. X
  499. X{
  500. X    register SPBLK * x;
  501. X
  502. X    if( NULL != ( x = q->root ) )
  503. X    while( x->leftlink != NULL )
  504. X        x = x->leftlink;
  505. X
  506. X    return( x );
  507. X
  508. X} /* spfhead */
  509. X
  510. X
  511. X
  512. X
  513. X/*----------------
  514. X *
  515. X * spftail() -- find the last node in a tree.
  516. X *
  517. X *    Fast version does not splay result or intermediate steps.
  518. X */
  519. XSPBLK *
  520. Xspftail( q )
  521. X
  522. XSPTREE * q;
  523. X
  524. X{
  525. X    register SPBLK * x;
  526. X
  527. X
  528. X    if( NULL != ( x = q->root ) )
  529. X    while( x->rightlink != NULL )
  530. X        x = x->rightlink;
  531. X
  532. X    return( x );
  533. X
  534. X} /* spftail */
  535. X
  536. X
  537. X/*----------------
  538. X *
  539. X * spscan() -- apply a function to nodes in ascending order.
  540. X *
  541. X *    if n is given, start at that node, otherwise start from
  542. X *    the head.
  543. X */
  544. Xvoid
  545. Xspscan( f, n, q )
  546. X
  547. Xregister int (*f)();
  548. Xregister SPBLK * n;
  549. Xregister SPTREE * q;
  550. X
  551. X{
  552. X    register SPBLK * x;
  553. X
  554. X    for( x = n != NULL ? n : spfhead( q ); x != NULL ; x = spfnext( x ) )
  555. X        (*f)( x );
  556. X}
  557. X
  558. X
  559. X
  560. X/*----------------
  561. X *
  562. X * sprscan() -- apply a function to nodes in descending order.
  563. X *
  564. X *    if n is given, start at that node, otherwise start from
  565. X *    the tail.
  566. X */
  567. Xvoid
  568. Xsprscan( f, n, q )
  569. X
  570. Xregister int (*f)();
  571. Xregister SPBLK * n;
  572. Xregister SPTREE * q;
  573. X
  574. X{
  575. X    register SPBLK *x;
  576. X
  577. X    for( x = n != NULL ? n : spftail( q ); x != NULL ; x = spfprev( x ) )
  578. X        (*f)( x );
  579. X}
  580. X
  581. X
  582. X
  583. X/*----------------
  584. X *
  585. X * spfnext() -- fast return next higer item in the tree, or NULL.
  586. X *
  587. X *    return the successor of n in q, represented as a splay tree.
  588. X *    This is a fast (on average) version that does not splay.
  589. X */
  590. XSPBLK *
  591. Xspfnext( n )
  592. X
  593. Xregister SPBLK * n;
  594. X
  595. X{
  596. X    register SPBLK * next;
  597. X    register SPBLK * x;
  598. X
  599. X    /* a long version, avoids splaying for fast average,
  600. X     * poor amortized bound
  601. X     */
  602. X
  603. X    if( n == NULL )
  604. X        return( n );
  605. X
  606. X    x = n->rightlink;
  607. X    if( x != NULL )
  608. X    {
  609. X        while( x->leftlink != NULL )
  610. X        x = x->leftlink;
  611. X        next = x;
  612. X    }
  613. X    else    /* x == NULL */
  614. X    {
  615. X        x = n->uplink;
  616. X        next = NULL;
  617. X        while( x != NULL )
  618. X    {
  619. X            if( x->leftlink == n )
  620. X        {
  621. X                next = x;
  622. X                x = NULL;
  623. X            }
  624. X        else
  625. X        {
  626. X                n = x;
  627. X                x = n->uplink;
  628. X            }
  629. X        }
  630. X    }
  631. X
  632. X    return( next );
  633. X
  634. X} /* spfnext */
  635. X
  636. X
  637. X
  638. X/*----------------
  639. X *
  640. X * spfprev() -- return fast previous node in a tree, or NULL.
  641. X *
  642. X *    return the predecessor of n in q, represented as a splay tree.
  643. X *    This is a fast (on average) version that does not splay.
  644. X */
  645. XSPBLK *
  646. Xspfprev( n )
  647. X
  648. Xregister SPBLK * n;
  649. X
  650. X{
  651. X    register SPBLK * prev;
  652. X    register SPBLK * x;
  653. X
  654. X    /* a long version,
  655. X     * avoids splaying for fast average, poor amortized bound
  656. X     */
  657. X
  658. X    if( n == NULL )
  659. X        return( n );
  660. X
  661. X    x = n->leftlink;
  662. X    if( x != NULL )
  663. X    {
  664. X        while( x->rightlink != NULL )
  665. X        x = x->rightlink;
  666. X        prev = x;
  667. X    }
  668. X    else
  669. X    {
  670. X        x = n->uplink;
  671. X        prev = NULL;
  672. X        while( x != NULL )
  673. X    {
  674. X            if( x->rightlink == n )
  675. X        {
  676. X                prev = x;
  677. X                x = NULL;
  678. X            }
  679. X        else
  680. X        {
  681. X                n = x;
  682. X                x = n->uplink;
  683. X            }
  684. X        }
  685. X    }
  686. X
  687. X    return( prev );
  688. X
  689. X} /* spfprev */
  690. X
  691. X
  692. X
  693. Xchar *
  694. Xspstats( q )
  695. XSPTREE *q;
  696. X{
  697. X    static char buf[ 128 ];
  698. X    float llen;
  699. X    float elen;
  700. X    float sloops;
  701. X
  702. X    if( q == NULL )
  703. X    return("");
  704. X
  705. X    llen = q->lookups ? (float)q->lkpcmps / q->lookups : 0;
  706. X    elen = q->enqs ? (float)q->enqcmps/q->enqs : 0;
  707. X    sloops = q->splays ? (float)q->splayloops/q->splays : 0;
  708. X
  709. X    sprintf(buf, "f(%d %4.2f) i(%d %4.2f) s(%d %4.2f)",
  710. X    q->lookups, llen, q->enqs, elen, q->splays, sloops );
  711. X
  712. X    return buf;
  713. X}
  714. X
  715. SHAR_EOF
  716. if test -f 'sptree.3'
  717. then
  718.     echo shar: over-writing existing file "'sptree.3'"
  719. fi
  720. sed 's/^X//' << \SHAR_EOF > 'sptree.3'
  721. X.TH SPTREE 3  "10 February 1988"
  722. X.UC 4
  723. X.SH NAME
  724. Xspdelete, spdeq, spempty, spenq, spenqafter, spenqbefore, spenqprior,
  725. Xspfhead, spfnext, spfprev, spftail, sphead, spinit, spinstall, splay,
  726. Xsplookup, spnext, spprev, sprscan, spscan, spstats \- splay tree operations
  727. X.SH SYNOPSIS
  728. X.nf
  729. X.B #include "sptree.h"
  730. X.PP
  731. X.B void spdelete(n, q)
  732. X.B SPBLK *n;
  733. X.B SPTREE *q;
  734. X.PP
  735. X.B SPBLK *spdeq(n)
  736. X.B SPBLK *n;
  737. X.PP
  738. X.B int spempty(q)
  739. X.B SPTREE *q;
  740. X.PP
  741. X.B SPBLK *spenq(n, q)
  742. X.B SPBLK *n;
  743. X.B SPTREE *q;
  744. X.PP
  745. X.B SPBLK *spenqafter(n, n1, q)
  746. X.B SPBLK *n, *n1;
  747. X.B SPTREE *q;
  748. X.PP
  749. X.B SPBLK *spenqbefore(n, n1, q)
  750. X.B SPBLK *n, *n1;
  751. X.B SPTREE *q;
  752. X.PP
  753. X.B SPBLK *spenqprior(n, q)
  754. X.B SPBLK *n;
  755. X.B SPTREE *q;
  756. X.PP
  757. X.B SPBLK *spfhead(q)
  758. X.B SPTREE *q;
  759. X.PP
  760. X.B SPBLK *spfnext(n)
  761. X.B SPBLK *n;
  762. X.PP
  763. X.B SPBLK *spfprev(n)
  764. X.B SPBLK *n;
  765. X.PP
  766. X.B SPBLK *spftail(q)
  767. X.B SPTREE *q;
  768. X.PP
  769. X.B SPBLK *sphead(q)
  770. X.B SPTREE *q;
  771. X.PP
  772. X.B SPTREE *spinit();
  773. X.PP
  774. X.B SPBLK *spinstall(key, data, datb, q)
  775. X.B char *key, *data, *datb;
  776. X.B SPTREE *q;
  777. X.PP
  778. X.B void splay(n, q)
  779. X.B SPBLK *n;
  780. X.B SPTREE *q;
  781. X.PP
  782. X.B SPBLK *splookup(key, q)
  783. X.B char *key;
  784. X.B SPTREE *q;
  785. X.PP
  786. X.B SPBLK *spnext(n, q)
  787. X.B SPBLK *n;
  788. X.B SPTREE *q;
  789. X.PP
  790. X.B SPBLK *spprev(n, q)
  791. X.B SPBLK *n;
  792. X.B SPTREE *q;
  793. X.PP
  794. X.B void sprscan(f, n, q)
  795. X.B int (*f)();
  796. X.B SPBLK *n;
  797. X.B SPTREE *q;
  798. X.PP
  799. X.B void spscan(f, n, q)
  800. X.B int (*f)();
  801. X.B SPBLK *n;
  802. X.B SPTREE *q;
  803. X.PP
  804. X.B char *spstats(q)
  805. X.B SPTREE *q;
  806. X.PP
  807. X.fi
  808. X.SH DESCRIPTION
  809. XThese functions operate on an event\-set or priority\-queue implemented
  810. Xusing splay trees.  These are similar to avl\-trees, but are not
  811. Xconcerned with keeping the tree strictly balanced.  Instead, the tree is
  812. Xdynamically reorganized in a simple way that yields a good amortized
  813. Xbound at the expense of worst case performance.
  814. X.PP
  815. XThe SPTREE structure declared in sptree.h should only be handled
  816. Xindirectly.  A pointer to an SPTREE is returned by
  817. X.I spinit
  818. Xand should be handed blindly to other access functions.
  819. X.PP
  820. XThe nodes in a splay tree are defined by the following structure,
  821. Xdeclared in sptree.h.
  822. X.PP
  823. X.nf
  824. Xtypedef struct _spblk SPBLK;
  825. Xtypedef struct _spblk
  826. X{
  827. X    .
  828. X    .
  829. X    .
  830. X
  831. X    char    *key;
  832. X    char    *data;
  833. X    char    *datb;
  834. X};
  835. X.fi
  836. X.PP
  837. XYou should only refer to the
  838. X.I key,
  839. X.I data
  840. Xand
  841. X.I datb
  842. Xmembers.
  843. X.PP
  844. XThe
  845. X.I key
  846. Xis interpreted as a pointer to a null terminated string, and ordering is
  847. Xdetermined by calls to the usual
  848. X.I strcmp
  849. Xroutine.
  850. X.PP
  851. XNo meaning is associated with the auxiliary members
  852. X.I data
  853. Xor
  854. X.I datb,
  855. Xand you are free to stuff them with whatever good conscience and a legal
  856. Xcast will allow.
  857. X.PP
  858. X.I Spdelete
  859. Xdeletes the node
  860. X.I n
  861. Xfrom the tree
  862. X.I q.
  863. XThe resulting tree is splayed around a new root, which is the successor
  864. Xto
  865. X.I n.
  866. X.PP
  867. X.I Spdeq
  868. Xremoves and returns the head node from the sub\-tree rooted at node
  869. X.I n.
  870. X.PP
  871. X.I Spempty
  872. Xreturns non\-zero if the tree
  873. X.I q
  874. Xhas no members.
  875. X.PP
  876. X.I Spenq
  877. Xinserts node
  878. X.I n
  879. Xinto tree
  880. X.I q
  881. Xafter all other nodes with the same key.  When this is done,
  882. X.I n
  883. Xwill be the root of the tree.
  884. X.PP
  885. X.I Spenqafter
  886. Xinserts node
  887. X.I n
  888. Xas the immediate sucessor of node
  889. X.I n1
  890. Xin tree
  891. X.I q.
  892. XIn so doing,
  893. X.I n1
  894. Xbecomes the root of the tree with
  895. X.I n
  896. Xas its right son.
  897. X.PP
  898. X.I Spenqbefore
  899. Xinserts node
  900. X.I n
  901. Xas the immediate predecessor of node
  902. X.I n1
  903. Xin tree
  904. X.I q.
  905. XIn doing so,
  906. X.I n1
  907. Xbecomes the root of the tree with
  908. X.I n
  909. Xas its left son.
  910. X.PP
  911. X.I Spenqprior
  912. Xinserts node
  913. X.I n
  914. Xinto the tree
  915. X.I q
  916. Xbefore all other nodes with the same key; after this is done,
  917. X.I n
  918. Xwill be the root of the tree.
  919. X.PP
  920. X.I Spfhead
  921. Xreturns a pointer to the head element in the tree
  922. X.I q,
  923. Xbut does not splay it to the root.
  924. X.PP
  925. X.I Spfnext
  926. Xreturns a pointer to the immediate successor of node
  927. X.I n
  928. Xwithout doing any reorganization.
  929. X.PP
  930. X.I Spfprev
  931. Xreturns a pointer to the immediate predecessor of node
  932. X.I n
  933. Xwithout doing any reoganization.
  934. X.PP
  935. X.I Spftail
  936. Xreturns a reference to the last node in the tree
  937. X.I q
  938. Xwithout doing any reorganization.
  939. X.PP
  940. X.I Sphead
  941. Xreturns a pointer to the head event in the tree
  942. X.I q.
  943. XThe returned node is made the root of the tree, as if
  944. X.I q
  945. Xhad been splayed around
  946. X.I n.
  947. X.PP
  948. X.I Spinit
  949. Xcreates a new splay tree using a \fImalloc\fP\-like routine named
  950. X.I emalloc
  951. Xthat must be supplied by the user.
  952. X.PP
  953. X.I Spinstall
  954. Xinserts an entry with the key value pointed to by
  955. X.I key
  956. Xwith the auxiliary values
  957. X.I data
  958. Xand
  959. X.I datb
  960. Xinto the tree
  961. X.I q.
  962. XIf a node with the key value already exists, its auxiliarly values are
  963. Xreplaced.  If the node does not already exist, a new one is allocated
  964. Xwith \fImalloc\fP\-like function named
  965. X.I emalloc
  966. Xthat must be supplied by the user.
  967. X.PP
  968. X.I Splay
  969. Xreorganizes the tree so that node
  970. X.I n
  971. Xbecomes the root of the tree in
  972. X.I q.
  973. XResults are unpredicatable if
  974. X.I n
  975. Xis not in
  976. X.I q
  977. Xto start with.
  978. X.I Q
  979. Xis split from
  980. X.I n
  981. Xup to the old root, with all nodes to the left of
  982. X.I n
  983. Xending up in the left sub\-tree, and all nodes to the right of
  984. X.I n
  985. Xending up in the right sub\-tree.  The left branch of the right
  986. Xsub\-tree and the right branch of the left sub\-tree are shortened in
  987. Xthe process.
  988. X.PP
  989. X.I Splookup
  990. Xsearches for a node containing the key value pointed to by
  991. X.I key
  992. Xin the tree
  993. X.I q.
  994. XA found node is splayed to the root and returned.  If the key is not
  995. Xfound, the function returns NULL and no reorganization is done.
  996. X.PP
  997. X.I
  998. XSpnext returns a pointer to the successor of
  999. X.I n
  1000. Xin
  1001. X.I q.
  1002. XThe successor becomes the root of the tree.
  1003. X.PP
  1004. X.I Spprev
  1005. Xreturns the predecessor of
  1006. X.I n
  1007. Xin
  1008. X.I q.
  1009. XThe predecessor becomes the root.
  1010. X.PP
  1011. X.I Sprscan
  1012. Xapplies the function
  1013. X.I f
  1014. Xstarting at node
  1015. X.I n
  1016. Xto the members of the tree
  1017. X.I q
  1018. Xin reverse order.  If
  1019. X.I n
  1020. Xis NULL, then the scan starts at the tail of the tree.  The tree is not
  1021. Xreorganized during the reverse scan.  The function is called with one
  1022. Xargument, a pointer to an SPBLK.  Its return value is ignored.
  1023. X.PP
  1024. X.I Spscan
  1025. Xapplies the function
  1026. X.I f
  1027. Xstarting at node
  1028. X.I n
  1029. Xin tree
  1030. X.I q
  1031. Xand all successive nodes, in order.  If
  1032. X.I n
  1033. Xis NULL, then the scan starts at the head of the tree.  The tree is not
  1034. Xreorganized during the scan.  The function is called with one argument,
  1035. Xa pointer to an SPBLK.  Its return value is ignored.
  1036. X.PP
  1037. X.I Spstats
  1038. Xreturns a string of statistics on the activities in the tree
  1039. X.I q.
  1040. XIt shows how many times
  1041. X.I splookup
  1042. Xwas called, and how many comparisons were needed per call,
  1043. Xthe number of nodes that have been added with
  1044. X.I spenq
  1045. Xand the number of comparisons needed per call, and finally, the number
  1046. Xof
  1047. X.I splay
  1048. Xoperations performed, and the number of loops done in each splay.  These
  1049. Xstatistics give an indication of the average effective depth of the tree
  1050. Xfor various operations.  The function returns a pointer to a static
  1051. Xbuffer that is overwritten with each call.
  1052. X.SH AUTHORS
  1053. XThe code was originally written in Pascal by Douglas W. Jones
  1054. X(jones@cs.uiowa.edu) with assistance from Srinivas R. Sataluri.  It was
  1055. Xtranslated to C with some new functions by Dave Brower
  1056. X(daveb@rtech.uucp).
  1057. X.SH REFERENCES
  1058. XThe basic splay tree algorithms were originally presented in:
  1059. X.PP
  1060. X.nf
  1061. X  Self Adjusting Binary Trees,
  1062. X  by D. D. Sleator and R. E. Tarjan,
  1063. X  Proc. ACM SIGACT Symposium on Theory
  1064. X  of Computing (Boston, Apr 1983) 235-245.
  1065. X.fi
  1066. X.PP
  1067. XMore operations on priority queues were added to help support discrete
  1068. Xevent simulation.  See, for example Chapter 14 of
  1069. X.PP
  1070. X.nf
  1071. X  Introduction to Simula 67,
  1072. X  by Gunther Lamprecht,
  1073. X  Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
  1074. X.fi
  1075. X.PP
  1076. Xand Chapter 9 of
  1077. X.PP
  1078. X.nf
  1079. X  Simula Begin,
  1080. X  by Graham M. Birtwistle, et al,
  1081. X  Studentlitteratur, Lund, 1979.
  1082. X.fi
  1083. X.PP
  1084. XSplay trees are compared with other data structures in
  1085. X.PP
  1086. X.nf
  1087. X  An Empirical Comparison of Priority-Queue and Event-Set Implementations,
  1088. X  by Douglas W. Jones,
  1089. X  Comm. ACM 29, 4 (Apr. 1986) 300-311.
  1090. X.fi
  1091. SHAR_EOF
  1092. if test -f 'sptree.c'
  1093. then
  1094.     echo shar: over-writing existing file "'sptree.c'"
  1095. fi
  1096. sed 's/^X//' << \SHAR_EOF > 'sptree.c'
  1097. X/*
  1098. X *
  1099. X *  sptree.c:  The following code implements the basic operations on
  1100. X *  an event-set or priority-queue implemented using splay trees:
  1101. X *
  1102. X *  SPTREE *spinit( compare )    Make a new tree
  1103. X *  int spempty();        Is tree empty?
  1104. X *  SPBLK *spenq( n, q )    Insert n in q after all equal keys.
  1105. X *  SPBLK *spdeq( q )        Return first key in q, removing it.
  1106. X *  SPBLK *spenqprior( n, q )    Insert n in q before all equal keys.
  1107. X *  void splay( n, q )        n (already in q) becomes the root.
  1108. X *
  1109. X *  In the above, n points to an SPBLK type, while q points to an
  1110. X *  SPTREE.
  1111. X *
  1112. X *  The implementation used here is based on the implementation
  1113. X *  which was used in the tests of splay trees reported in:
  1114. X *
  1115. X *    An Empirical Comparison of Priority-Queue and Event-Set Implementations,
  1116. X *    by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311.
  1117. X *
  1118. X *  The changes made include the addition of the enqprior
  1119. X *  operation and the addition of up-links to allow for the splay
  1120. X *  operation.  The basic splay tree algorithms were originally
  1121. X *  presented in:
  1122. X *
  1123. X *    Self Adjusting Binary Trees,
  1124. X *        by D. D. Sleator and R. E. Tarjan,
  1125. X *            Proc. ACM SIGACT Symposium on Theory
  1126. X *            of Computing (Boston, Apr 1983) 235-245.
  1127. X *
  1128. X *  The enq and enqprior routines use variations on the
  1129. X *  top-down splay operation, while the splay routine is bottom-up.
  1130. X *  All are coded for speed.
  1131. X *
  1132. X *  Written by:
  1133. X *    Douglas W. Jones
  1134. X *
  1135. X *  Translated to C by:
  1136. X *    David Brower, daveb@rtech.uucp
  1137. X *
  1138. X */
  1139. X
  1140. X# include "sptree.h"
  1141. X
  1142. X/* USER SUPPLIED! */
  1143. X
  1144. Xextern char *emalloc();
  1145. X
  1146. X
  1147. X/*----------------
  1148. X *
  1149. X * spinit() -- initialize an empty splay tree
  1150. X *
  1151. X */
  1152. XSPTREE *
  1153. Xspinit()
  1154. X{
  1155. X    register SPTREE * q;
  1156. X
  1157. X    q = (SPTREE *) emalloc( sizeof( *q ) );
  1158. X
  1159. X    q->lookups = 0;
  1160. X    q->lkpcmps = 0;
  1161. X    q->enqs = 0;
  1162. X    q->enqcmps = 0;
  1163. X    q->splays = 0;
  1164. X    q->splayloops = 0;
  1165. X    q->root = NULL;
  1166. X    return( q );
  1167. X}
  1168. X
  1169. X/*----------------
  1170. X *
  1171. X * spempty() -- is an event-set represented as a splay tree empty?
  1172. X */
  1173. Xint
  1174. Xspempty( q )
  1175. X
  1176. XSPTREE *q;
  1177. X
  1178. X{
  1179. X    return( q == NULL || q->root == NULL );
  1180. X}
  1181. X
  1182. X
  1183. X/*----------------
  1184. X *
  1185. X *  spenq() -- insert item in a tree.
  1186. X *
  1187. X *  put n in q after all other nodes with the same key; when this is
  1188. X *  done, n will be the root of the splay tree representing q, all nodes
  1189. X *  in q with keys less than or equal to that of n will be in the
  1190. X *  left subtree, all with greater keys will be in the right subtree;
  1191. X *  the tree is split into these subtrees from the top down, with rotations
  1192. X *  performed along the way to shorten the left branch of the right subtree
  1193. X *  and the right branch of the left subtree
  1194. X */
  1195. XSPBLK *
  1196. Xspenq( n, q )
  1197. X
  1198. Xregister SPBLK * n;
  1199. Xregister SPTREE * q;
  1200. X
  1201. X{
  1202. X    register SPBLK * left;    /* the rightmost node in the left tree */
  1203. X    register SPBLK * right;    /* the leftmost node in the right tree */
  1204. X    register SPBLK * next;    /* the root of the unsplit part */
  1205. X    register SPBLK * temp;
  1206. X
  1207. X    register char * key;
  1208. X    register int Sct;        /* Strcmp value */
  1209. X
  1210. X    q->enqs++;
  1211. X    n->uplink = NULL;
  1212. X    next = q->root;
  1213. X    q->root = n;
  1214. X    if( next == NULL )    /* trivial enq */
  1215. X    {
  1216. X        n->leftlink = NULL;
  1217. X        n->rightlink = NULL;
  1218. X    }
  1219. X    else        /* difficult enq */
  1220. X    {
  1221. X        key = n->key;
  1222. X        left = n;
  1223. X        right = n;
  1224. X
  1225. X        /* n's left and right children will hold the right and left
  1226. X       splayed trees resulting from splitting on n->key;
  1227. X       note that the children will be reversed! */
  1228. X
  1229. X    q->enqcmps++;
  1230. X        if ( STRCMP( next->key, key ) > 0 )
  1231. X        goto two;
  1232. X
  1233. X    one:    /* assert next->key <= key */
  1234. X
  1235. X    do    /* walk to the right in the left tree */
  1236. X    {
  1237. X            temp = next->rightlink;
  1238. X            if( temp == NULL )
  1239. X        {
  1240. X                left->rightlink = next;
  1241. X                next->uplink = left;
  1242. X                right->leftlink = NULL;
  1243. X                goto done;    /* job done, entire tree split */
  1244. X            }
  1245. X
  1246. X        q->enqcmps++;
  1247. X            if( STRCMP( temp->key, key ) > 0 )
  1248. X        {
  1249. X                left->rightlink = next;
  1250. X                next->uplink = left;
  1251. X                left = next;
  1252. X                next = temp;
  1253. X                goto two;    /* change sides */
  1254. X            }
  1255. X
  1256. X            next->rightlink = temp->leftlink;
  1257. X            if( temp->leftlink != NULL )
  1258. X            temp->leftlink->uplink = next;
  1259. X            left->rightlink = temp;
  1260. X            temp->uplink = left;
  1261. X            temp->leftlink = next;
  1262. X            next->uplink = temp;
  1263. X            left = temp;
  1264. X            next = temp->rightlink;
  1265. X            if( next == NULL )
  1266. X        {
  1267. X                right->leftlink = NULL;
  1268. X                goto done;    /* job done, entire tree split */
  1269. X            }
  1270. X
  1271. X        q->enqcmps++;
  1272. X
  1273. X    } while( STRCMP( next->key, key ) <= 0 );    /* change sides */
  1274. X
  1275. X    two:    /* assert next->key > key */
  1276. X
  1277. X    do    /* walk to the left in the right tree */
  1278. X    {
  1279. X            temp = next->leftlink;
  1280. X            if( temp == NULL )
  1281. X        {
  1282. X                right->leftlink = next;
  1283. X                next->uplink = right;
  1284. X                left->rightlink = NULL;
  1285. X                goto done;    /* job done, entire tree split */
  1286. X            }
  1287. X
  1288. X        q->enqcmps++;
  1289. X            if( STRCMP( temp->key, key ) <= 0 )
  1290. X        {
  1291. X                right->leftlink = next;
  1292. X                next->uplink = right;
  1293. X                right = next;
  1294. X                next = temp;
  1295. X                goto one;    /* change sides */
  1296. X            }
  1297. X            next->leftlink = temp->rightlink;
  1298. X            if( temp->rightlink != NULL )
  1299. X            temp->rightlink->uplink = next;
  1300. X            right->leftlink = temp;
  1301. X            temp->uplink = right;
  1302. X            temp->rightlink = next;
  1303. X            next->uplink = temp;
  1304. X            right = temp;
  1305. X            next = temp->leftlink;
  1306. X            if( next == NULL )
  1307. X        {
  1308. X                left->rightlink = NULL;
  1309. X                goto done;    /* job done, entire tree split */
  1310. X            }
  1311. X
  1312. X        q->enqcmps++;
  1313. X
  1314. X    } while( STRCMP( next->key, key ) > 0 );    /* change sides */
  1315. X
  1316. X        goto one;
  1317. X
  1318. X    done:    /* split is done, branches of n need reversal */
  1319. X
  1320. X        temp = n->leftlink;
  1321. X        n->leftlink = n->rightlink;
  1322. X        n->rightlink = temp;
  1323. X    }
  1324. X
  1325. X    return( n );
  1326. X
  1327. X} /* spenq */
  1328. X
  1329. X
  1330. X/*----------------
  1331. X *
  1332. X *  spdeq() -- return and remove head node from a subtree.
  1333. X *
  1334. X *  remove and return the head node from the node set; this deletes
  1335. X *  (and returns) the leftmost node from q, replacing it with its right
  1336. X *  subtree (if there is one); on the way to the leftmost node, rotations
  1337. X *  are performed to shorten the left branch of the tree
  1338. X */
  1339. XSPBLK *
  1340. Xspdeq( n )
  1341. X
  1342. Xregister SPBLK * n;
  1343. X
  1344. X{
  1345. X    register SPBLK * deq;        /* one to return */
  1346. X    register SPBLK * next;           /* the next thing to deal with */
  1347. X    register SPBLK * left;          /* the left child of next */
  1348. X    register SPBLK * farleft;        /* the left child of left */
  1349. X    register SPBLK * farfarleft;    /* the left child of farleft */
  1350. X
  1351. X    if( n == NULL )
  1352. X    {
  1353. X        deq = NULL;
  1354. X    }
  1355. X    else
  1356. X    {
  1357. X        next = n;
  1358. X        left = next->leftlink;
  1359. X        if( left == NULL )
  1360. X    {
  1361. X            deq = next;
  1362. X            n = next->rightlink;
  1363. X            if( n != NULL )
  1364. X        n->uplink = NULL;
  1365. X        }
  1366. X    else for(;;)
  1367. X    {
  1368. X            /* next is not it, left is not NULL, might be it */
  1369. X            farleft = left->leftlink;
  1370. X            if( farleft == NULL )
  1371. X        {
  1372. X                deq = left;
  1373. X                next->leftlink = left->rightlink;
  1374. X                if( left->rightlink != NULL )
  1375. X            left->rightlink->uplink = next;
  1376. X        break;
  1377. X            }
  1378. X
  1379. X            /* next, left are not it, farleft is not NULL, might be it */
  1380. X            farfarleft = farleft->leftlink;
  1381. X            if( farfarleft == NULL )
  1382. X        {
  1383. X                deq = farleft;
  1384. X                left->leftlink = farleft->rightlink;
  1385. X                if( farleft->rightlink != NULL )
  1386. X            farleft->rightlink->uplink = left;
  1387. X        break;
  1388. X            }
  1389. X
  1390. X            /* next, left, farleft are not it, rotate */
  1391. X            next->leftlink = farleft;
  1392. X            farleft->uplink = next;
  1393. X            left->leftlink = farleft->rightlink;
  1394. X            if( farleft->rightlink != NULL )
  1395. X        farleft->rightlink->uplink = left;
  1396. X            farleft->rightlink = left;
  1397. X            left->uplink = farleft;
  1398. X            next = farleft;
  1399. X            left = farfarleft;
  1400. X    }
  1401. X    }
  1402. X
  1403. X    return( deq );
  1404. X
  1405. X} /* spdeq */
  1406. X
  1407. X
  1408. X/*----------------
  1409. X *
  1410. X *  spenqprior() -- insert into tree before other equal keys.
  1411. X *
  1412. X *  put n in q before all other nodes with the same key; after this is
  1413. X *  done, n will be the root of the splay tree representing q, all nodes in
  1414. X *  q with keys less than that of n will be in the left subtree, all with
  1415. X *  greater or equal keys will be in the right subtree; the tree is split
  1416. X *  into these subtrees from the top down, with rotations performed along
  1417. X *  the way to shorten the left branch of the right subtree and the right
  1418. X *  branch of the left subtree; the logic of spenqprior is exactly the
  1419. X *  same as that of spenq except for a substitution of comparison
  1420. X *  operators
  1421. X */
  1422. XSPBLK *
  1423. Xspenqprior( n, q )
  1424. X
  1425. Xregister SPBLK * n;
  1426. XSPTREE * q;
  1427. X
  1428. X{
  1429. X
  1430. X    register SPBLK * left;    /* the rightmost node in the left tree */
  1431. X    register SPBLK * right;    /* the leftmost node in the right tree */
  1432. X    register SPBLK * next;    /* the root of unsplit part of tree */
  1433. X    register SPBLK * temp;
  1434. X    register int Sct;        /* Strcmp value */
  1435. X    register char *key;
  1436. X
  1437. X    n->uplink = NULL;
  1438. X    next = q->root;
  1439. X    q->root = n;
  1440. X    if( next == NULL )    /* trivial enq */
  1441. X    {
  1442. X        n->leftlink = NULL;
  1443. X        n->rightlink = NULL;
  1444. X    }
  1445. X    else        /* difficult enq */
  1446. X    {
  1447. X        key = n->key;
  1448. X        left = n;
  1449. X        right = n;
  1450. X
  1451. X        /* n's left and right children will hold the right and left
  1452. X       splayed trees resulting from splitting on n->key;
  1453. X       note that the children will be reversed! */
  1454. X
  1455. X        if( STRCMP( next->key, key ) >= 0 )
  1456. X        goto two;
  1457. X
  1458. X    one:    /* assert next->key < key */
  1459. X
  1460. X    do    /* walk to the right in the left tree */
  1461. X    {
  1462. X            temp = next->rightlink;
  1463. X            if( temp == NULL )
  1464. X        {
  1465. X                left->rightlink = next;
  1466. X                next->uplink = left;
  1467. X                right->leftlink = NULL;
  1468. X                goto done;    /* job done, entire tree split */
  1469. X            }
  1470. X            if( STRCMP( temp->key, key ) >= 0 )
  1471. X        {
  1472. X                left->rightlink = next;
  1473. X                next->uplink = left;
  1474. X                left = next;
  1475. X                next = temp;
  1476. X                goto two;    /* change sides */
  1477. X            }
  1478. X            next->rightlink = temp->leftlink;
  1479. X            if( temp->leftlink != NULL )
  1480. X        temp->leftlink->uplink = next;
  1481. X            left->rightlink = temp;
  1482. X            temp->uplink = left;
  1483. X            temp->leftlink = next;
  1484. X            next->uplink = temp;
  1485. X            left = temp;
  1486. X            next = temp->rightlink;
  1487. X            if( next == NULL )
  1488. X        {
  1489. X                right->leftlink = NULL;
  1490. X                goto done;    /* job done, entire tree split */
  1491. X            }
  1492. X
  1493. X    } while( STRCMP( next->key, key ) < 0 );    /* change sides */
  1494. X
  1495. X    two:    /* assert next->key >= key */
  1496. X
  1497. X    do     /* walk to the left in the right tree */
  1498. X    {
  1499. X            temp = next->leftlink;
  1500. X            if( temp == NULL )
  1501. X        {
  1502. X                right->leftlink = next;
  1503. X                next->uplink = right;
  1504. X                left->rightlink = NULL;
  1505. X                goto done;    /* job done, entire tree split */
  1506. X            }
  1507. X            if( STRCMP( temp->key, key ) < 0 )
  1508. X        {
  1509. X                right->leftlink = next;
  1510. X                next->uplink = right;
  1511. X                right = next;
  1512. X                next = temp;
  1513. X                goto one;    /* change sides */
  1514. X            }
  1515. X            next->leftlink = temp->rightlink;
  1516. X            if( temp->rightlink != NULL )
  1517. X        temp->rightlink->uplink = next;
  1518. X            right->leftlink = temp;
  1519. X            temp->uplink = right;
  1520. X            temp->rightlink = next;
  1521. X            next->uplink = temp;
  1522. X            right = temp;
  1523. X            next = temp->leftlink;
  1524. X            if( next == NULL )
  1525. X        {
  1526. X                left->rightlink = NULL;
  1527. X                goto done;    /* job done, entire tree split */
  1528. X            }
  1529. X
  1530. X    } while( STRCMP( next->key, key ) >= 0 );    /* change sides */
  1531. X
  1532. X        goto one;
  1533. X
  1534. X    done:    /* split is done, branches of n need reversal */
  1535. X
  1536. X        temp = n->leftlink;
  1537. X        n->leftlink = n->rightlink;
  1538. X        n->rightlink = temp;
  1539. X    }
  1540. X
  1541. X    return( n );
  1542. X
  1543. X} /* spenqprior */
  1544. X
  1545. X/*----------------
  1546. X *
  1547. X *  splay() -- reorganize the tree.
  1548. X *
  1549. X *  the tree is reorganized so that n is the root of the
  1550. X *  splay tree representing q; results are unpredictable if n is not
  1551. X *  in q to start with; q is split from n up to the old root, with all
  1552. X *  nodes to the left of n ending up in the left subtree, and all nodes
  1553. X *  to the right of n ending up in the right subtree; the left branch of
  1554. X *  the right subtree and the right branch of the left subtree are
  1555. X *  shortened in the process
  1556. X *
  1557. X *  this code assumes that n is not NULL and is in q; it can sometimes
  1558. X *  detect n not in q and complain
  1559. X */
  1560. X
  1561. Xvoid
  1562. Xsplay( n, q )
  1563. X
  1564. Xregister SPBLK * n;
  1565. XSPTREE * q;
  1566. X
  1567. X{
  1568. X    register SPBLK * up;    /* points to the node being dealt with */
  1569. X    register SPBLK * prev;    /* a descendent of up, already dealt with */
  1570. X    register SPBLK * upup;    /* the parent of up */
  1571. X    register SPBLK * upupup;    /* the grandparent of up */
  1572. X    register SPBLK * left;    /* the top of left subtree being built */
  1573. X    register SPBLK * right;    /* the top of right subtree being built */
  1574. X
  1575. X    left = n->leftlink;
  1576. X    right = n->rightlink;
  1577. X    prev = n;
  1578. X    up = prev->uplink;
  1579. X
  1580. X    q->splays++;
  1581. X
  1582. X    while( up != NULL )
  1583. X    {
  1584. X    q->splayloops++;
  1585. X
  1586. X        /* walk up the tree towards the root, splaying all to the left of
  1587. X       n into the left subtree, all to right into the right subtree */
  1588. X
  1589. X        upup = up->uplink;
  1590. X        if( up->leftlink == prev )    /* up is to the right of n */
  1591. X    {
  1592. X            if( upup != NULL && upup->leftlink == up )  /* rotate */
  1593. X        {
  1594. X                upupup = upup->uplink;
  1595. X                upup->leftlink = up->rightlink;
  1596. X                if( upup->leftlink != NULL )
  1597. X            upup->leftlink->uplink = upup;
  1598. X                up->rightlink = upup;
  1599. X                upup->uplink = up;
  1600. X                if( upupup == NULL )
  1601. X            q->root = up;
  1602. X        else if( upupup->leftlink == upup )
  1603. X            upupup->leftlink = up;
  1604. X        else
  1605. X            upupup->rightlink = up;
  1606. X                up->uplink = upupup;
  1607. X                upup = upupup;
  1608. X            }
  1609. X            up->leftlink = right;
  1610. X            if( right != NULL )
  1611. X        right->uplink = up;
  1612. X            right = up;
  1613. X
  1614. X        }
  1615. X    else                /* up is to the left of n */
  1616. X    {
  1617. X            if( upup != NULL && upup->rightlink == up )    /* rotate */
  1618. X        {
  1619. X                upupup = upup->uplink;
  1620. X                upup->rightlink = up->leftlink;
  1621. X                if( upup->rightlink != NULL )
  1622. X            upup->rightlink->uplink = upup;
  1623. X                up->leftlink = upup;
  1624. X                upup->uplink = up;
  1625. X                if( upupup == NULL )
  1626. X            q->root = up;
  1627. X        else if( upupup->rightlink == upup )
  1628. X            upupup->rightlink = up;
  1629. X        else
  1630. X            upupup->leftlink = up;
  1631. X                up->uplink = upupup;
  1632. X                upup = upupup;
  1633. X            }
  1634. X            up->rightlink = left;
  1635. X            if( left != NULL )
  1636. X        left->uplink = up;
  1637. X            left = up;
  1638. X        }
  1639. X        prev = up;
  1640. X        up = upup;
  1641. X    }
  1642. X
  1643. X# ifdef DEBUG
  1644. X    if( q->root != prev )
  1645. X    {
  1646. X/*    fprintf(stderr, " *** bug in splay: n not in q *** " ); */
  1647. X    abort();
  1648. X    }
  1649. X# endif
  1650. X
  1651. X    n->leftlink = left;
  1652. X    n->rightlink = right;
  1653. X    if( left != NULL )
  1654. X    left->uplink = n;
  1655. X    if( right != NULL )
  1656. X    right->uplink = n;
  1657. X    q->root = n;
  1658. X    n->uplink = NULL;
  1659. X
  1660. X} /* splay */
  1661. X
  1662. SHAR_EOF
  1663. if test -f 'sptree.h'
  1664. then
  1665.     echo shar: over-writing existing file "'sptree.h'"
  1666. fi
  1667. sed 's/^X//' << \SHAR_EOF > 'sptree.h'
  1668. X/*
  1669. X** sptree.h:  The following type declarations provide the binary tree
  1670. X**  representation of event-sets or priority queues needed by splay trees
  1671. X**
  1672. X**  assumes that data and datb will be provided by the application
  1673. X**  to hold all application specific information
  1674. X**
  1675. X**  assumes that key will be provided by the application, comparable
  1676. X**  with the compare function applied to the addresses of two keys.
  1677. X*/
  1678. X
  1679. X# ifndef SPTREE_H
  1680. X# define SPTREE_H
  1681. X
  1682. X# ifndef NULL
  1683. X# define NULL    0
  1684. X# endif
  1685. X
  1686. X# define STRCMP( a, b ) ( (Sct = *(a) - *(b)) ? Sct : strcmp( (a), (b) ) )
  1687. X
  1688. Xtypedef struct _spblk SPBLK;
  1689. X
  1690. Xtypedef struct _spblk
  1691. X{
  1692. X    SPBLK    * leftlink;
  1693. X    SPBLK    * rightlink;
  1694. X    SPBLK    * uplink;
  1695. X
  1696. X    char    * key;        /* formerly time/timetyp */
  1697. X    char    * data;        /* formerly aux/auxtype */
  1698. X    char    * datb;
  1699. X};
  1700. X
  1701. Xtypedef struct
  1702. X{
  1703. X    SPBLK    * root;        /* root node */
  1704. X
  1705. X    /* Statistics, not strictly necessary, but handy for tuning  */
  1706. X
  1707. X    int        lookups;    /* number of splookup()s */
  1708. X    int        lkpcmps;    /* number of lookup comparisons */
  1709. X    
  1710. X    int        enqs;        /* number of spenq()s */
  1711. X    int        enqcmps;    /* compares in spenq */
  1712. X    
  1713. X    int        splays;
  1714. X    int        splayloops;
  1715. X
  1716. X} SPTREE;
  1717. X
  1718. X
  1719. X/* sptree.c */
  1720. Xextern SPTREE * spinit();    /* init tree */
  1721. Xextern int spempty();        /* is tree empty? */
  1722. Xextern SPBLK * spenq();        /* insert item into the tree */
  1723. Xextern SPBLK * spdeq();        /* return and remove lowest item in subtree */
  1724. Xextern SPBLK * spenqprior();    /* insert before items with same key */
  1725. Xextern void splay();        /* reorganize tree */
  1726. X
  1727. X/* spaux.c */
  1728. Xextern SPBLK * sphead();    /* return first node in tree */
  1729. Xextern void spdelete();        /* delete node from tree */
  1730. Xextern SPBLK * spnext();    /* return next node in tree */
  1731. Xextern SPBLK * spprev();    /* return previous node in tree */
  1732. Xextern SPBLK * spenqbefore();    /* enqueue before existing node */
  1733. Xextern SPBLK * spenqafter();    /* enqueue after existing node */
  1734. X
  1735. X/* spdaveb.c */
  1736. Xextern SPBLK * splookup();    /* find key in a tree */
  1737. Xextern SPBLK * spinstall();    /* enter an item, allocating or replacing */
  1738. Xextern SPBLK * sptail();    /* find end of a tree */
  1739. Xextern void spscan();        /* scan forward through tree */
  1740. Xextern void sprscan();        /* reverse scan through tree */
  1741. Xextern SPBLK * spfnext();    /* fast non-splaying next */
  1742. Xextern SPBLK * spfprev();    /* fast non-splaying prev */
  1743. X
  1744. X# endif
  1745. SHAR_EOF
  1746. #    End of shell archive
  1747. exit 0
  1748.  
  1749.  
  1750.